For example, to authenticate users, various systems acquire biological information of each of the users, and determine whether biological information agreeing with the acquired biological information is present in a pre-registered database. The biological information acquired at the time of the authentication rarely completely agrees with the biological information acquired at the time of the registration, so that similarity search is effective.
Techniques have been developed in which, when the similarity search is performed, feature values of biological information are converted into hash vectors as an expression of a degree of similarity, and pieces of the biological information are identified as similar pieces of biological information when the Hamming distance between the hash vectors thereof is small.
Some related techniques employ processing of converting the feature values into the hash vectors using a hyperplane while other related techniques employ processing of converting the feature values into the hash vectors using a hypersphere, which is more likely to improve accuracy than using the hyperplane.
Conventional technologies are described, for example, in the following patent documents:
Japanese Laid-open Patent Publication No. 10-247243; and
Japanese Laid-open Patent Publication No. 2009-133798.
Some other related technologies are described, for example, in the following non-patent documents:
M. Datar, N. Immorlica, P. Indyk, V. S. Mirrokni, “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”, Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG 2004;
Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-Eui Yoon, “Spherical Hashing”, In CVPR, pp. 2957-2964, 2012; and
Kengo Terasawa and Yuzuru Tanaka, “Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere”, In Frank K. H. A. Dehne, Jorg-Rudiger Sack, and Norbert Zeh, editors, WADS, Vol. 4619 of Lecture Notes in Computer Science, pp. 27-38, Springer, 2007.
However, it is difficult to accurately perform the similarity search using feature value vectors, which is a problem.
Suppose that the position of a projective point is adjusted so as to inversely stereographically project the feature value data on only a surface of a hypersphere S on the side facing a feature value space. After the adjustment, feature value data may be entered. In such a case, the feature value data may also be inversely stereographically projected on the surface of the hypersphere S on the side opposite to the feature value space across the hypersphere S, so that a shortcut of a point at infinity may occur between pieces of the feature value data that have been inversely stereographically projected.
FIG. 29 is a diagram for explaining the shortcut of the point at infinity. The point at infinity in a feature value space V is projected to one point on the north pole of the hypersphere S. As a result, for example, an inverse stereographic projection of a point p sufficiently far from a point Xo in the feature value space V associates the point p with a point p′ on the hypersphere S; and an inverse stereographic projection of a point q in the feature value space V associates the point q with a point q′ on the hypersphere S. Such inverse stereographic projections cause the shortcut to occur. For example, in some cases, a path 10b passing near the point at infinity is shorter than a path 10a passing near the origin of the feature value space V. Such cases may make the distance between points apart from each other by a distance 10c in the feature value space V smaller on the hypersphere S, and, as a result, the Hamming distance between the bit strings of the point p and the point q may be reduced.